This invention relates to a storage system having a memory hierarchy for a data processor with virtual storage.
A storage system having a memory hierarachy is provided with a main storage and a buffer storage. The buffer storage is adapted to retain as a copy part of the data kept in the main storage. The capacity of the buffer storage is low compared to that of the main storage MS, but it operates at a higher speed than the main storage, and is capable of accessing at high speed the data required in a processor. Methods of controlling the buffer storage include an associative register method and a set associative method (which is also called a "congruent method"). The set associative method, which has a higher use efficiency, is employed in most cases.
FIG. 1 shows the relationship between the buffer storage BS and the main storage MS in the set associative system. In the example shown in FIG. 1, the buffer storage BS is divided into columns 0-127, each of which consists of four blocks or rows. One row consists, for example, of 32 bytes, and is capable of storing 32 successive bytes of data in the main storage MS. The main storage MS is divided logically into the same number of columns as the buffer storage BS and the number of rows in each column in the main storage MS is determined by the memory capacity thereof. If the main storage MS has a capacity of four megabytes (4096KB), as shown in FIG. 1, each column has 1024 rows and each row consists of 32 bytes. The data stored in one of the four rows in the corresponding column in the buffer storage BS. The main storage address, which is not shown in FIG. 1, of an effective data block stored in the buffer storage BS is retained in a buffer address array BAA, which has the same construction as the buffer storage BS. The number of storage areas in the buffer address array BAA is the same as the number of rows in the buffer storage BS.
A data processing system with a memory hierarchy employs a virtual memory to give the programmer freedom to prepare a program which is larger than the capacity of the main storage MS. Virtual storage in practice consists of a main storage MS and an auxiliary storage AS. These storage areas are divided into units called pages, for example, of 2 KB, and the contents of the storages are swapped on the basis of these units. Some of the pages of a virtual storage are in main storage MS, and the remaining pages, which cannot be held in MS, are in auxiliary storage AS. The pages in auxiliary storage AS are read into (paged in) the main storage MS when needed, and written out (paged out) to auxiliary storage AS when they are not needed.
In a data processing system with virtual storage, a program is written by its address (logical address) in the virtual storage. Accordingly, the logical address is translated by the processor into a processable address (real address) in the main storage MS. The translation of a logical address into a real address is done by a dynamic address translation mechanism, which includes a translation lookaside buffer TLB for retaining address translation pairs each consisting of a logical address and a real address corresponding thereto, for the purpose of executing an efficient address translation.
In the basic operation of a storage system employing both virtual storage and buffer storage, it is necessary initially to ascertain that the real address corresponding to a memory reference logical address is retained by the translation lookaside buffer TLB. When the real address is retained by the translation lookaside buffer TLB, the real address is obtained immediately therefrom. It is then necessary to ascertain that the real address is retained by the buffer address array BAA. When the real address is retained by the buffer address array BAA, the buffer storage BS is accessed to obtain the desired data. However, as is apparent, this two-step procedure requires an undesirably-lengthy access time.
Some conventional methods have been developed with a view to shortening the access time, including a method which provides for referencing the translation lookaside buffer TLB and the buffer address array BAA in parallel and thereafter referencing the buffer storage BS, and a method in which the translation lookaside buffer TLB, buffer address array BAA and the buffer storage BS are all referenced in parallel. These methods are disclosed in U.S. Pat. No. 3,761,881 and Japanese Patent Application No. 28341/1977.
FIG. 2 shows a storage system in which the translation lookaside buffer TLB, the buffer address array BAA and the buffer storage BS are referenced in parallel. Referring to FIG. 2, reference numeral 1 denotes a logical address register LAR, an output from which forms the reference addresses applied to a translation lookaside buffer TLB 2, a buffer address array BAA 3 and a buffer storage BS 6. The translation lookaside buffer TLB 2 translates a logical address on a line 11 into a real address and sets that real address in a register TLBR 20. The real address set in the register TLBR 20 is sent to a comparator circuit 4 over a line 12.
The buffer address array BAA 3 stores therein real addresses representing the position in main storage MS of the data buffered in the buffer storage BS 6. However, certain bits of each real address are identical to certain bits of the corresponding logical address. On this basis, it is possible to read out the real addresses from the buffer address array BAA 3 designated by the logical address received from the logical address register LAR 41 and set these addresses in a register 21. These real addresses are then sent to the comparator circuit 4 over a line 13. The comparator circuit 4 compares the real addresses on the lines 12, 13 and when these real addresses agree with each other, it indicates that the data required by the processor is in the buffer store BS 6. This is called the "IN-BS state".
In the buffer storage BS in a set associative system having N columns.times.M rows, a plurality (M) of rows in the corresponding column in the buffer address array BAA 3 are read out simultaneously and input to the comparator circuit 4 over the line 13. When an IN-BS condition has been determined in the comparator circuit 4, the row number agreeing with the real address on the line 12 is set in a row number register 24 by the comparator circuit.
At the same time, the buffer storage BS 6 is accessed by an address set in a BS address register BSAR 5 by the logical address register LAR 1. A block, the unit of data registered in the buffer storage BS 6, is generally divided into L banks. For ease of explanation, if L is 2, 1 block is divided into an even bank and an odd bank. In this case, the data read out from the buffer storage BS 6 accessed by the address in the buffer storage address register BSAR 5 has a width of sixteen bytes. Of the data read out from the buffer storage BS 6, the eight bytes of data with even-numbered block addresses are set in a data register (BDR (E)) 7, and the eight bytes of data with odd-numbered block addresses in a data register (BDR (O)) 8. A number M BDRs 7, 8 are provided corresponding to the rows in the buffer storage BS 6, and the data in M rows in the column designated by the buffer storage address register BSAR 5 are read out. A selector 23 selects one of the data registers BDR 7, 8 corresponding to the row number designated by the row number register ROWR 24, and transfers 16 bytes of data to an aligner 9. The aligner 9 left-shifts or right-shifts the sixteen bytes of data in accordance with the address and outputs eight bytes of data required by the processor. The eight bytes of data from the aligner 9 are set in a fetch data register FDR 10 and transferred to the processor. An example of the aligner used is disclosed in Japaense Patent Laid-Open No. 94133/1978.
FIG. 3 is a timing chart of the operation of the storage system shown in FIG. 2. To simplify the explanation let n.sub.i be a stage corresponding to one machine cycle. A starting point, at which a logical address has been set in the logical address register LAR 1, is the "n.sub.0 stage", and the following stages are "n.sub.1, n.sub.2 . . . ". The timing operations are carried out in two phases T.sub.0, T.sub.1 within one machine cycle. Referring to FIG. 3, the translation lookaside buffer TLB 2 and the buffer address array BAA 3 are read in parallel in accordance with a logical address in the logical address register LAR 1, real addresses are compared in the comparator 4, and a row number is then set in the row number register ROWR 24. These operations are carried out during two machine cycles. Data read from the buffer storage BS is set in the data regiser BDR 1.5 cycles after the starting point.
Referring to FIG. 3, the time t.sub.1 required to determine the row number of the buffer storage BS on the basis of the results obtained from the translation lookaside buffer TLB and the buffer address array BAA, which are referenced in parallel, becomes longer than the time t.sub.2 required to verify the data from the buffer storage BS, the reading of which starts at the same time. The buffer storage reference time with respect to the operation of the processor is determined on the basis of the time t.sub.1. After the row number of the buffer storage BS has been determined by the row number register ROWR 24, sixteen bytes of the buffer storage BS reading data corresponding to the row number are transferred to the aligner 9 by a selector 23. After the data has been aligned, the required eight bytes of data are set in a fetch data register FDR 10. Thus, it takes 2.5 machine cycles (MC) after a logical address has been set in the logical address register LAR 1 to set the required data in the fetch data register FDR 10.